package BinarySearch;

class Solution {
    public int[] searchRange(int[] nums, int target) {
         if (nums == null || nums.length == 0)return new int[]{-1,-1};
         int[] ans = new int[2];
         int leftResult =0 , rightResult=0;
         int left = 0 , right = nums.length-1;
         // 细节1 : left < right , 不能等于等于的话有可能死循环
        // 这个是找左端点的情况,  所以
        // 为什么不能分等于 , 因为你找到的相等的位置不一定是最左端的位置
         while (left < right){
             // 细节2 mid不能用加1的那种情况会让循环退不出去
             int mid = left+(right-left)/2;
             if (nums[mid] < target){
                 left = mid+1;
             }else if (nums[mid] >= target){
                 right = mid;
             }
         }
         if (nums[left] == target)ans[0] = nums[left];
         else return new int[]{-1,-1};
         left = 0;
         right= nums.length-1;
        while (left < right){
            // 细节2 mid不能用加1的那种情况会让循环退不出去
            int mid = left+(right-left+1)/2;
            if (nums[mid] <= target){
                left = mid;
            }else if (nums[mid] > target){
                right = mid-1;
            }
        }
        if (nums[left] == target)ans[1] = nums[left];
        else return new int[]{-1,-1};
        return ans;
    }
    public int mySqrt(int x) {
        // 细节 x 可能是小于1 的
        if (x < 1)return 0;
        long left =1 ,right =x;
        while (left < right){
            long mid = left+(right-left+1)/2;
            if (mid*mid <= x){
                left = mid;
            }else {
                right = mid-1;
            }
        }
        return (int)left;
    }

}